#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<int>> combine(int n, int k)
    {
        trace_back(n, k, 1, 0);
        return _ans;
    }

private:
    void trace_back(int n, int k, int curNum, int count)
    {
        if (count == k) {
            _ans.emplace_back(_v);
            return;
        }

        if (n - curNum + 1 < k - count) {
            return;
        }

        _v.push_back(curNum);
        trace_back(n, k, curNum + 1, count + 1);
        _v.pop_back();

        trace_back(n, k, curNum + 1, count);
    }

    std::vector<int> _v;
    std::vector<std::vector<int>> _ans;
};